package graphBasics.iterator;

import java.util.Vector;

/**
 * 稀疏图-邻接表
 * mxf
 */
public class SparseGraph {

    private int n, m; // n点数， m边数
    private boolean directed; // 是否为有向图
    private Vector<Integer>[] g; // 具体数据

    public SparseGraph(int n, boolean directed) {
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }

    public int V(){ return n;} // 返回节点个数
    public int E(){ return m;} // 返回边的个数

    // 判断v到w是否连接
    public boolean hasEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >=0 && w < n;

        for(int i = 0; i < g[v].size(); i++) {
            if(g[v].get(i) == w) {
                return true;
            }
        }
        return false;
    }

    public void addEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >=0 && w < n;
        // 允许存在平行边的问题
//        if(hasEdge(v, w))
//            return;
        g[v].add(w);
        if(v != w && !directed) {
            g[w].add(v);
        }
        m++;
    }

    // 返回图中一个顶点的所有邻边
    // 由于java使用引用机制，返回一个Vector不会带来额外开销,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}
